/*
 *  osbf_aux.c 
 *  
 *  This software is licensed to the public under the Free Software
 *  Foundation's GNU GPL, version 2.  You may obtain a copy of the
 *  GPL by visiting the Free Software Foundations web site at
 *  www.fsf.org, and a copy is included in this distribution.  
 *
 * Copyright 2005, 2006  Fidelis Assis, all rights reserved.
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <inttypes.h>

#include "osbflib.h"

/* Version names */
const char *db_version_names[] = {
  "SBPH-Markovian",
  "OSB-Bayes",
  "Correlate",
  "Neural",
  "OSB-Winnow",
  "OSBF-Bayes",
  "Unknown"
};

uint32_t microgroom_chain_length = OSBF_MICROGROOM_CHAIN_LENGTH;
uint32_t microgroom_stop_after = OSBF_MICROGROOM_STOP_AFTER;

/*
 * Pack a chain moving buckets to a place closer to their
 * right positions whenever possible, using the buckets marked as free.
 * At the end, all buckets still marked as free are zeroed.
 */
void
osbf_packchain (CLASS_STRUCT * class, uint32_t packstart, uint32_t packlen)
{
  uint32_t packend, ifrom, ito, free_start;
  uint32_t thash;

  packend = packstart + packlen;
  if (packend >= NUM_BUCKETS (class))
    packend -= NUM_BUCKETS (class);

#ifdef DEBUG_packchain
  {
    uint32_t i, rp, d, h;
    fprintf (stderr, "Before packing\n");
    for (i = packstart; i != packend; i = NEXT_BUCKET (class, i))
      {
	h = BUCKET_HASH (class, i);
	rp = HASH_INDEX (class, h);
	if (i >= rp)
	  d = i - rp;
	else
	  d = NUM_BUCKETS (class) + i - rp;
	fprintf (stderr, " i: %5" PRIu32 " d: %3" PRIu32 " value: %" PRIu32
		 " h: %08X flags: %02X\n", i, d, BUCKET_VALUE (class, i),
		 h, BUCKET_FLAGS (class, i));
      }
  }
#endif

  /* search the first marked-free bucket */
  for (free_start = packstart;
       free_start != packend; free_start = NEXT_BUCKET (class, free_start))
    if (MARKED_FREE (class, free_start))
      break;

  if (free_start != packend)
    {
      for (ifrom = NEXT_BUCKET (class, free_start);
	   ifrom != packend; ifrom = NEXT_BUCKET (class, ifrom))
	{
	  if (!MARKED_FREE (class, ifrom))
	    {
	      /* see if there's a free bucket closer to its right place */
	      thash = BUCKET_HASH (class, ifrom);
	      ito = HASH_INDEX (class, thash);

	      while (ito != ifrom && !MARKED_FREE (class, ito))
		ito = NEXT_BUCKET (class, ito);

	      /* if found a marked-free bucket, use it */
	      if (MARKED_FREE (class, ito))
		{
		  /* copy bucket and flags */
		  BUCKET_HASH (class, ito) = thash;
		  BUCKET_KEY (class, ito) = BUCKET_KEY (class, ifrom);
		  BUCKET_VALUE (class, ito) = BUCKET_VALUE (class, ifrom);
		  BUCKET_FLAGS (class, ito) = BUCKET_FLAGS (class, ifrom);
		  /* mark the from bucket as free */
		  MARK_IT_FREE (class, ifrom);
		}
	    }
	}
    }

#ifdef DEBUG_packchain
  {
    uint32_t i, rp, d, h;
    fprintf (stderr, "Before zeroing\n");
    for (i = packstart; i != packend; i = NEXT_BUCKET (class, i))
      {
	h = BUCKET_HASH (class, i);
	rp = HASH_INDEX (class, h);
	if (i >= rp)
	  d = i - rp;
	else
	  d = NUM_BUCKETS (class) + i - rp;
	fprintf (stderr, " i: %5" PRIu32 " d: %3" PRIu32 " value: %" PRIu32
		 " h: %08X flags: %02X\n", i, d, BUCKET_VALUE (class, i),
		 h, BUCKET_FLAGS (class, i));
      }
  }
#endif

  for (ito = packstart; ito != packend; ito = NEXT_BUCKET (class, ito))
    if (MARKED_FREE (class, ito))
      {
	BUCKET_VALUE (class, ito) = 0;
	UNMARK_IT_FREE (class, ito);
      }

#ifdef DEBUG_packchain
  {
    uint32_t i, rp, d, h;
    fprintf (stderr, "After packing\n");
    for (i = packstart; i != packend; i = NEXT_BUCKET (class, i))
      {
	h = BUCKET_HASH (class, i);
	rp = HASH_INDEX (class, h);
	if (i >= rp)
	  d = i - rp;
	else
	  d = NUM_BUCKETS (class) + i - rp;
	fprintf (stderr, " i: %5" PRIu32 " d: %3" PRIu32 " value: %" PRIu32
		 " h: %08X flags: %02X\n", i, d, BUCKET_VALUE (class, i),
		 h, BUCKET_FLAGS (class, i));
      }
  }
#endif

}


/*
 * Prune and pack a chain in a class database
 * Returns the number of freed (zeroed) buckets
 */
uint32_t
osbf_microgroom (CLASS_STRUCT * class, uint32_t bindex)
{
  uint32_t i_aux, j_aux, right_position;
  static uint32_t microgroom_count = 0;
  uint32_t packstart, packlen;
  uint32_t zeroed_countdown, min_value, min_value_any;
  uint32_t distance, max_distance;
  uint32_t groom_locked = OSBF_MICROGROOM_LOCKED;

  j_aux = 0;
  zeroed_countdown = microgroom_stop_after;

  i_aux = j_aux = 0;
  microgroom_count++;

  /*  move to start of chain that overflowed,
   *  then prune just that chain.
   */
  min_value = OSBF_MAX_BUCKET_VALUE;
  i_aux = j_aux = HASH_INDEX (class, bindex);
  min_value_any = BUCKET_VALUE (class, i_aux);

  if (!BUCKET_IN_CHAIN (class, i_aux))
    return 0;			/* initial bucket not in a chain! */

  while (BUCKET_IN_CHAIN (class, i_aux))
    {
      if (BUCKET_VALUE (class, i_aux) < min_value_any)
	min_value_any = BUCKET_VALUE (class, i_aux);
      if (BUCKET_VALUE (class, i_aux) < min_value &&
	  !BUCKET_IS_LOCKED (class, i_aux))
	min_value = BUCKET_VALUE (class, i_aux);
      i_aux = PREV_BUCKET (class, i_aux);
      if (i_aux == j_aux)
	break;			/* don't hang if we have a 100% full .css file */
      /* fprintf (stderr, "-"); */
    }

  /*  now, move the index to the first bucket in this chain. */
  i_aux = NEXT_BUCKET (class, i_aux);
  packstart = i_aux;
  /* find the end of the chain */
  while (BUCKET_IN_CHAIN (class, i_aux))
    {
      i_aux = NEXT_BUCKET (class, i_aux);
      if (i_aux == packstart)
	break;			/* don't hang if we have a 100% full .cfc file */
    }
  /*  now, the index is right after the last bucket in this chain. */

  /* only >, not >= in this case, otherwise the packlen would be 0
   * instead of NUM_BUCKETS (class).
   */
  if (i_aux > packstart)
    packlen = i_aux - packstart;
  else				/* if i_aux == packstart, packlen = header->buckets */
    packlen = NUM_BUCKETS (class) + i_aux - packstart;

  /* if no unlocked bucket can be zeroed, zero any */
  if (groom_locked > 0 || min_value == OSBF_MAX_BUCKET_VALUE)
    {
      groom_locked = 1;
      min_value = min_value_any;
    }
  else
    groom_locked = 0;

/*
 *   This pruning method zeroes buckets with minimum count in the chain.
 *   It tries first buckets with minimum distance to their right position,
 *   to increase the chance of zeroing older buckets first. If none with
 *   distance 0 is found, the distance is increased until at least one
 *   bucket is zeroed.
 *
 *   We keep track of how many buckets we've marked to be zeroed and we
 *   stop marking additional buckets after that point. That messes up
 *   the tail length, and if we don't repack the tail, then features in
 *   the tail can become permanently inaccessible! Therefore, we really
 *   can't stop in the middle of the tail (well, we could stop marking,
 *   but we need to pass the full length of the tail in).
 * 
 *   This is a statistics report of microgroomings for 4147 messages
 *   of the SpamAssassin corpus. It shows that 77% is done in a single
 *   pass, 95.2% in 1 or 2 passes and 99% in at most 3 passes.
 *
 *   # microgrommings   passes   %    accum. %
 *        232584           1    76.6   76.6
 *         56396           2    18.6   95.2
 *         11172           3     3.7   98.9
 *          2502           4     0.8   99.7
 *           726           5     0.2   99.9
 *           ...
 *   -----------
 *        303773
 *
 *   If we consider only the last 100 microgroomings, when the cfc
 *   file is full, we'll have the following numbers showing that most
 *   microgroomings (61%) are still done in a single pass, almost 90%
 *   is done in 1 or 2 passes and 97% are done in at most 3 passes:
 *
 *   # microgrommings   passes   %    accum. %
 *          61             1    61      61
 *          27             2    27      88
 *           9             3     9      97
 *           3             4     3     100
 *         ---
 *         100
 *
 *   So, it's not so slow. Anyway, a better algorithm could be
 *   implemented using 2 additional arrays, with MICROGROOM_STOP_AFTER
 *   positions each, to store the indexes of the candidate buckets
 *   found with distance equal to 1 or 2 while we scan for distance 0.
 *   Those with distance 0 are zeroed immediatelly. If none with
 *   distance 0 is found, we'll zero the indexes stored in the first
 *   array. Again, if none is found in the first array, we'll try the
 *   second one. Finally, if none is found in both arrays, the loop
 *   will continue until one bucket is zeroed.
 *
 *   But now comes the question: do the numbers above justify the
 *   additional code/work? I'll try to find out the answer
 *   implementing it :), but this has low priority for now.
 *
 */


  /* try features in their right place first */
  max_distance = 1;
  /* fprintf(stderr, "packstart: %ld,  packlen: %ld, max_zeroed_buckets: %ld\n",
     packstart, packlen, microgroom_stop_after); */

  /* while no bucket is zeroed...  */
  while (zeroed_countdown == microgroom_stop_after)
    {
      /*
         fprintf(stderr, "Start: %lu, stop_after: %u, max_distance: %lu,
         min_value: %lu\n", packstart,
         microgroom_stop_after, max_distance, min_value);
       */
      i_aux = packstart;
      while (BUCKET_IN_CHAIN (class, i_aux) && zeroed_countdown > 0)
	{
	  /* check if it's a candidate */
	  if ((BUCKET_VALUE (class, i_aux) == min_value) &&
	      (!BUCKET_IS_LOCKED (class, i_aux) || (groom_locked != 0)))
	    {
	      /* if it is, check the distance */
	      right_position = HASH_INDEX (class, BUCKET_HASH (class, i_aux));
	      if (right_position <= i_aux)
		distance = i_aux - right_position;
	      else
		distance = NUM_BUCKETS (class) + i_aux - right_position;
	      if (distance < max_distance)
		{
		  MARK_IT_FREE (class, i_aux);
		  zeroed_countdown--;
		}
	    }
	  i_aux++;
	  if (i_aux >= NUM_BUCKETS (class))
	    i_aux = 0;
	}

      /*  if none was zeroed, increase the allowed distance between the */
      /*  candidade's position and its right place. */
      if (zeroed_countdown == microgroom_stop_after)
	max_distance++;
    }

  /*
     fprintf (stderr,
     "Leaving microgroom: %ld buckets with value %ld zeroed at distance %ld\n",
     microgroom_stop_after - zeroed_countdown, h[i].value, max_distance - 1);
   */

  /* now we pack the chains */
  osbf_packchain (class, packstart, packlen);

  /* return the number of zeroed buckets */
  return (microgroom_stop_after - zeroed_countdown);
}


/* get next bucket index */
uint32_t
osbf_next_bindex (CLASS_STRUCT * class, uint32_t bindex)
{
  bindex++;
  if (bindex >= NUM_BUCKETS (class))
    bindex = 0;
  return bindex;
}

/* get the index of the last bucket in a chain */
uint32_t
osbf_last_in_chain (CLASS_STRUCT * class, uint32_t bindex)
{
  uint32_t wraparound;

  /* if the bucket is not in a chain, return an index */
  /* out of the buckets space, equal to the number of */
  /* buckets in the file to indicate an empty chain */
  if (!BUCKET_IN_CHAIN (class, bindex))
    return NUM_BUCKETS (class);

  wraparound = bindex;
  while (BUCKET_IN_CHAIN (class, bindex))
    {
      bindex++;
      if (bindex >= NUM_BUCKETS (class))
	bindex = 0;

      /* if .cfc file is full return an index out of */
      /* the buckets space, equal to number of buckets */
      /* in the file, plus one */
      if (bindex == wraparound)
	return NUM_BUCKETS (class) + 1;
    }

  if (bindex == 0)
    bindex = NUM_BUCKETS (class) - 1;
  else
    bindex--;

  return bindex;
}


/* get previous bucket index */
uint32_t
osbf_prev_bindex (CLASS_STRUCT * class, uint32_t bindex)
{
  if (bindex == 0)
    bindex = NUM_BUCKETS (class) - 1;
  else
    bindex--;
  return bindex;
}

/* get the index of the first bucket in a chain */
uint32_t
osbf_first_in_chain (CLASS_STRUCT * class, uint32_t bindex)
{
  uint32_t wraparound;

  /* if the bucket is not in a chain, return an index */
  /* out of the buckets space, equal to the number of */
  /* buckets in the file to indicate an empty chain */
  if (!BUCKET_IN_CHAIN (class, bindex))
    return NUM_BUCKETS (class);

  wraparound = bindex;
  while (BUCKET_IN_CHAIN (class, bindex))
    {
      if (bindex == 0)
	bindex = NUM_BUCKETS (class) - 1;
      else
	bindex--;

      /* if .cfc file is full return an index out of */
      /* the buckets space, equal to number of buckets */
      /* in the file, plus one */
      if (bindex == wraparound)
	return NUM_BUCKETS (class) + 1;
    }

  bindex++;
  if (bindex >= NUM_BUCKETS (class))
    bindex = 0;

  return bindex;
}


uint32_t
osbf_find_bucket (CLASS_STRUCT * class, uint32_t hash, uint32_t key)
{
  uint32_t bindex, start;

  bindex = start = HASH_INDEX (class, hash);
  while (BUCKET_IN_CHAIN (class, bindex) &&
	 !BUCKET_HASH_COMPARE (class, bindex, hash, key))
    {
      bindex = NEXT_BUCKET (class, bindex);

      /* if .cfc file is completely full return an index */
      /* out of the buckets space, equal to number of buckets */
      /* in the file, plus one */
      if (bindex == start)
	return NUM_BUCKETS (class) + 1;
    }

  /* return the index of the found bucket or, if not found,
   * the index of a free bucket where it could be put
   */
  return bindex;
}

void
osbf_update_bucket (CLASS_STRUCT * class, uint32_t bindex, int delta)
{

  /*
   * fprintf (stderr, "Bucket updated at %lu, hash: %lu, key: %lu, value: %d\n",
   *       bindex, hashes[bindex].hash, hashes[bindex].key, delta);
   */

  if (delta > 0 &&
      BUCKET_VALUE (class, bindex) + delta >= OSBF_MAX_BUCKET_VALUE)
    {
      SETL_BUCKET_VALUE (class, bindex, OSBF_MAX_BUCKET_VALUE);
    }
  else if (delta < 0 && BUCKET_VALUE (class, bindex) <= (uint32_t) (-delta))
    {
      if (BUCKET_VALUE (class, bindex) != 0)
	{
	  uint32_t i, packlen;

	  MARK_IT_FREE (class, bindex);

	  /* pack chain */
	  i = osbf_last_in_chain (class, bindex);
	  if (i >= bindex)
	    packlen = i - bindex + 1;
	  else
	    packlen = NUM_BUCKETS (class) - (bindex - i) + 1;
/*
	    fprintf (stderr, "packing: %" PRIu32 ", %" PRIu32 "\n", i,
		     bindex);
*/
	  osbf_packchain (class, bindex, packlen);
	}
    }
  else
    {
      SETL_BUCKET_VALUE (class, bindex, BUCKET_VALUE (class, bindex) + delta);
    }
}



void
osbf_insert_bucket (CLASS_STRUCT * class,
		    uint32_t bindex, uint32_t hash, uint32_t key, int value)
{
  uint32_t right_index, distance;
  int microgroom = 1;

  /* "right" bucket index */
  right_index = HASH_INDEX (class, hash);
  /* distance from right position to free position */
  distance = (bindex >= right_index) ? bindex - right_index :
    NUM_BUCKETS (class) - (right_index - bindex);

  if (microgroom && (value > 0))
    while (distance > microgroom_chain_length)
      {
	/*
	 * fprintf (stderr, "hindex: %lu, bindex: %lu, distance: %lu\n",
	 *          hindex, bindex, distance);
	 */
	osbf_microgroom (class, PREV_BUCKET (class, bindex));
	/* get new free bucket index */
	bindex = osbf_find_bucket (class, hash, key);
	distance = (bindex >= right_index) ? bindex - right_index :
	  NUM_BUCKETS (class) - (right_index - bindex);
      }

  /*
   *   fprintf (stderr,
   *   "new bucket at %lu, hash: %lu, key: %lu, distance: %lu\n",
   *         bindex, hash, key, distance);
   */

  SETL_BUCKET_VALUE (class, bindex, value);
  BUCKET_HASH (class, bindex) = hash;
  BUCKET_KEY (class, bindex) = key;
}


uint32_t
strnhash (unsigned char *str, uint32_t len)
{
  uint32_t i;
#ifdef CRM114_COMPATIBILITY
  int32_t hval;			/* signed int for CRM114 compatibility */
#else
  uint32_t hval;
#endif
  uint32_t tmp;

  /* initialize hval */
  hval = len;

  /*  for each character in the incoming text: */
  for (i = 0; i < len; i++)
    {
      /*
       *  xor in the current byte against each byte of hval
       *  (which alone gaurantees that every bit of input will have
       *  an effect on the output)
       */

      tmp = str[i];
      tmp = tmp | (tmp << 8) | (tmp << 16) | (tmp << 24);
      hval ^= tmp;

      /*    add some bits out of the middle as low order bits. */
      hval = hval + ((hval >> 12) & 0x0000ffff);

      /*     swap most and min significative bytes */
      tmp = (hval << 24) | ((hval >> 24) & 0xff);
      hval &= 0x00ffff00;	/* zero most and least significative bytes of hval */
      hval |= tmp;		/* OR with swapped bytes */

      /*    rotate hval 3 bits to the left (thereby making the */
      /*    3rd msb of the above mess the hsb of the output hash) */
      hval = (hval << 3) + (hval >> 29);
    }
  return (uint32_t) hval;
}


static OSBF_HEADER_BUCKET_UNION hu;
int
osbf_create_cfcfile (const char *cfcfile, uint32_t num_buckets,
		     uint32_t major, uint32_t minor, char *errmsg)
{
  FILE *f;
  uint32_t i_aux;
  OSBF_BUCKET_STRUCT bucket = { 0, 0, 0 };

  if (cfcfile == NULL || *cfcfile == '\0')
    {
      if (cfcfile != NULL)
	snprintf (errmsg, OSBF_ERROR_MESSAGE_LEN,
		  "Invalid file name: '%s'", cfcfile);
      else
	strncpy (errmsg, "Invalid (NULL) pointer to cfc file name",
		 OSBF_ERROR_MESSAGE_LEN);
      return -1;
    }

  f = fopen (cfcfile, "w");
  if (!f)
    {
      snprintf (errmsg, OSBF_ERROR_MESSAGE_LEN,
		"Couldn't create the file: '%s'", cfcfile);
      return -1;
    }

  /* Set the header. */
  hu.header.version = major;
  hu.header.db_flags = minor;
  hu.header.buckets_start = OSBF_CFC_HEADER_SIZE;
  hu.header.num_buckets = num_buckets;
  hu.header.learnings = 0;

  /* Write header */
  if (fwrite (&hu, sizeof (hu), 1, f) != 1)
    {
      snprintf (errmsg, OSBF_ERROR_MESSAGE_LEN,
		"Couldn't initialize the file header: '%s'", cfcfile);
      return -1;
    }

  /*  Initialize CFC hashes - zero all buckets */
  for (i_aux = 0; i_aux < num_buckets; i_aux++)
    {
      /* Write buckets */
      if (fwrite (&bucket, sizeof (bucket), 1, f) != 1)
	{
	  snprintf (errmsg, OSBF_ERROR_MESSAGE_LEN,
		    "Couldn't write to: '%s'", cfcfile);
	  return -1;
	}
    }
  fclose (f);
  return 0;
}
